#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void get(int index, vector<int> &S, vector<vector<int> > &ans, vector<int> &cur)
{
   if (index == S.size()) {
       ans.push_back(cur);
       return;  
   }
   cur.push_back(S[index]);
   get(index+1, S, ans, cur);
   cur.pop_back();
   get(index+1, S, ans, cur);
}

class Solution {
    public:
        vector<vector<int> > subsets(vector<int> &S) {
	    sort(S.begin(), S.end());
            vector<vector<int> > ans;
            if (S.size() == 0) return ans;
            vector<int> cur;
            get(0, S, ans, cur); 
            return ans;
        }
};
//add one more code
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ans;
        for (int i = 0; i < (1 << S.size()); i++) {
            vector<int>  cur;
            for (int j = 0; j < S.size(); j++) 
                if (i && (1 << j)) 
                    cur.push_back(S[j]);
            ans.push_back(cur);
        }   
        return ans;
    } 

int main(int argc, char **argv)
{
    Solution mySolution;
    vector<int> input;
    input.push_back(1);
    input.push_back(2);
    input.push_back(3);
    cout << "-----------------Test 1--------------------" << endl;
    vector<vector<int> > result = mySolution.subsets(input);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++)
            cout << result[i][j] << " ";
        cout << endl;
    }

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;


    return 0;
}
